'''
 This class is an test of how to use the BST tree class.
 
 author: Samuel T. C. Santos
 data  : 2013/14/04
 
'''
from bst import BST
from node import Node

class BSTTest:

	def __init__(self):
		print("init BST tests...")

	def runTestPostOrder(self):
		bst = BST()

		bst.insert(7)
		assert(bst.postOrder() == [7])

		bst.insert(5)
		assert(bst.postOrder() ==[5, 7])

		bst.insert(11)
		assert(bst.postOrder() ==[5, 11, 7])

		bst.insert(31)
		assert(bst.postOrder() ==[5, 31, 11, 7])
		
		bst.insert(-1)
		assert(bst.postOrder() ==[-1, 5, 31, 11, 7])
		
		bst.insert(6)
		bst.insert(9)
		bst.insert(17)
		bst.insert(3)
		bst.insert(21)
		bst.insert(15)
		
		post = [3, -1, 6, 5, 9, 15, 21, 17, 31, 11, 7]

		assert(bst.postOrder() == post)
				
		print("Done, test Post Order OK!")

	def runTestPreOrder(self):
		bst = BST()

		bst.insert(7)
		assert(bst.preOrder() == [7])

		bst.insert(5)
		assert(bst.preOrder() == [7, 5])

		bst.insert(11)
		assert(bst.preOrder() == [7, 5,11])

		bst.insert(31)
		assert(bst.preOrder() == [7, 5,11, 31])

		bst.insert(-1)
		assert(bst.preOrder() == [7, 5, -1, 11, 31])

		bst.insert(6)
		assert(bst.preOrder() == [7, 5, -1, 6, 11, 31])

		bst.insert(9)
		assert(bst.preOrder() == [7, 5, -1, 6, 11, 9, 31])

		bst.insert(17)
		assert(bst.preOrder() == [7, 5, -1, 6, 11, 9, 31, 17])

		bst.insert(3)
		assert(bst.preOrder() == [7, 5, -1, 3, 6, 11, 9, 31, 17])
		

		print("Done, test Pre Order OK!")

		

	def runTestOrder(self):
		bst = BST()

		bst.insert(7)
		assert(bst.order() == [7])

		bst.insert(5)
		assert(bst.order() == [5, 7])

		bst.insert(11)
		assert(bst.order() == [5, 7, 11])

		bst.insert(31)
		assert(bst.order() == [5, 7, 11, 31])

		bst.insert(-1)
		assert(bst.order() == [-1, 5, 7, 11, 31])

		bst.insert(6)
		assert(bst.order() == [-1, 5, 6, 7, 11, 31])

		bst.insert(9)
		assert(bst.order() == [-1, 5, 6, 7, 9, 11, 31])

		bst.insert(17)
		assert(bst.order() == [-1, 5, 6, 7, 9, 11, 17, 31])

		bst.insert(3)
		assert(bst.order() == [-1, 3, 5, 6, 7, 9, 11, 17, 31])

		bst.insert(21)
		assert(bst.order() == [-1, 3, 5, 6, 7, 9, 11, 17, 21, 31])

		bst.insert(15)
		assert(bst.order() == [-1, 3, 5, 6, 7, 9 ,11, 15,  17, 21, 31])

		print("Done, test Order OK!")
		
		

	def runTestRemove(self):
		bst = BST()

		assert(bst.size() == 0)
		root = bst.getRoot()

		assert(root.isLeaf() == True)

		bst.insert(12)

		assert(bst.size() == 1)
		assert(bst.height() == 0)
		assert(bst.order() == [12])

		bst.remove(12)

		assert(bst.order() == [])
		assert(bst.size() == 0)

		bst.insert(5)
		bst.insert(3)

		assert( bst.order() == [3, 5])
		
		root = bst.getRoot()

		assert( root.getData() == 5)
		
		bst.remove(3)
		
		assert(bst.order() ==[5])
		
		bst.insert(10)
		bst.insert(3)
		bst.insert(13)

		assert(bst.order() == [3, 5, 10, 13])

		bst.remove(10)

		assert(bst.order() == [3, 5, 13])
		root = bst.getRoot()

		assert(root.getData() == 5)
		
		successor = bst.successor(5)

		assert(successor.getData() == 13)


		bst.remove(5)

		assert(bst.order() == [3, 13])

		bst.remove(3)
		assert(bst.order() == [13])

		bst.remove(13)

		assert(bst.order() == [])

		print("Done, test Remove OK!")


	def runTestHeight(self):
		bst = BST()
		
		assert( bst.height() == -1)
		
		bst.insert(10)
		assert( bst.height() == 0)

		bst.insert(15)
		assert( bst.height() == 1)

		bst.insert(7)
		assert( bst.height() == 1)

		bst.insert(12)
		assert( bst.height() == 2)

		
		print("Done, test height OK!")
	
	
	def runTestSucessor(self):
		bst = BST()
		
		node = bst.successor(0)
		assert(node.getData() == None)
		
		bst.insert(5)
		
		node = bst.successor(5)
		assert(node.getData() == None)
		assert(node.isLeaf == True)

		bst.insert(13)
		node = bst.successor(5)
		assert(node.getData() == 13)
		
		node = bst.successor(13)
		assert(node.getData() == None)
	
		bst.insert(-1)
		node = bst.successor(-1)
		assert(node.getData() == 5)
		
		bst.insert(9)
		node = bst.successor(9)
		assert(node.getData() == 13)
		
		bst.insert(7)
		node = bst.successor(7)
		assert(node.getData() == 9)
		
		bst.insert(0)
		node = bst.successor(0)
		assert(node.getData() == 5)
		
		bst.insert(4)
		node = bst.successor(4)
		assert(node.getData() == 5)
	
		bst.insert(-3)
		node = bst.successor(-3)
		assert(node.getData() == -1)
		
		bst.insert(12)
		node = bst.successor(12)
		assert(node.getData() == 13)
		
		bst.insert(21)
		node = bst.successor(21)
		assert(node.getData() == None)
		
		print("Done, test Successor OK!")
		
	'''
	Minimum return the minumum value stored into the tree.
	'''
	def runTestMinimum(self):
		bst = BST()
		
		node = bst.minimum()
		assert( node.getData() == None)
		
		bst.insert(5)
		
		node = bst.minimum()
		assert( node.getData() == 5)
		
		bst.insert(13)

		node = bst.minimum()
		assert( node.getData() == 5)
		
		bst.insert(-1)
		
		node = bst.minimum()
		assert( node.getData() == -1)
		
		bst.insert(9)

		node = bst.minimum()
		assert( node.getData() == -1)

		bst.insert(7)
		
		node = bst.minimum()
		assert( node.getData() == -1)
		
		bst.insert(0)
		node = bst.minimum()
		assert( node.getData() == -1)
		
		bst.insert(4)
		node = bst.minimum()
		assert( node.getData() == -1)
		
		bst.insert(-3)
		node = bst.minimum()
		assert( node.getData() == -3)
		
		bst.insert(12)
		node = bst.minimum()
		assert( node.getData() == -3)
		
		bst.insert(21)
		
		node = bst.minimum()
		assert( node.getData() == -3)
		
		print("Done, test Minimum OK!")
		
	def runTestMaximum(self):
		bst = BST()
		
		node = bst.maximum()
		
		assert( node.getData() == None) 
		
		bst.insert(5)
		
		node = bst.maximum()
		assert( node.getData() == 5)
		
		bst.insert(13)

		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(-1)
		
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(9)

		node = bst.maximum()
		assert( node.getData() == 13)

		bst.insert(7)
		
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(0)
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(4)
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(-3)
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(12)
		node = bst.maximum()
		assert( node.getData() == 13)
		
		bst.insert(21)
		
		node = bst.maximum()
		assert( node.getData() == 21)
		
		print("Done, test Maximum OK!")
		
		
		
	'''
	 Tests for the method search of the BST.
	 
	'''
	def runTestSearch(self):
		bst = BST()
		node = bst.search(1)
		assert( node.getData() == None )
		
		bst.insert(11)
		node = bst.search(11)
		
		assert( node.getData() == 11 )
		
		bst.insert(7)
		bst.insert(13)
		bst.insert(-1)
		bst.insert(9)
		bst.insert(2)
		bst.insert(15)
		bst.insert(12)
		bst.insert(21)
		
		node = bst.search(7)
		assert( node.getData() == 7)

		node = bst.search(13)
		assert( node.getData() == 13)

		node = bst.search(-1)
		assert( node.getData() == -1)

		node = bst.search(9)
		assert( node.getData() == 9)

		node = bst.search(2)
		assert( node.getData() == 2)

		node = bst.search(15)
		assert( node.getData() == 15)

		node = bst.search(21)
		assert( node.getData() == 21)
		
		node = bst.search(0)
		assert( node.getData() == None)
		
		print("Done, test search OK!")
	
	'''
	 Test for the method insert of the BST.
	'''
	def runTestInsert(self):
		'''
		insert numbers : [11, 7, 13, -1, 9, 2, 15, 12, 21] 
		
		                  11
					    /    \
					   7      13
					  / \    /  \
					-1   9  12  15
					  \           \
					   2           21
		
		walk order : [-1, 2, 7, 9, 11, 12, 13 , 15, 21]
		'''
		bst = BST()
		
		assert(bst.getRoot().isEmpty() == True)
		assert(bst.getRoot().getLeft() == None)
		assert(bst.getRoot().getRight() == None)
		assert(bst.getRoot().getParent().isEmpty() == True)
		assert(bst.getRoot().getData()== None)
		assert(bst.getRoot().isRoot() == True)

		assert(bst.isEmpty() == True)
		
		bst.insert(11)
		assert (bst.order() == [11])
		assert(bst.getRoot().getData() == 11)
		assert (bst.isEmpty() == False)
		
		bst.insert(7)
		assert(bst.order() == [7, 11])
		assert(bst.getRoot().getData() == 11)
		
		bst.insert(13)
		assert(bst.order() == [7, 11, 13])
		
		bst.insert(-1)
		assert(bst.order() == [-1, 7, 11, 13])
		
		bst.insert(9)
		assert(bst.order() == [-1, 7, 9, 11, 13])
		
		bst.insert(2)
		assert(bst.order() == [-1, 2, 7, 9, 11, 13])
		
		bst.insert(15)
		assert(bst.order() == [-1, 2, 7, 9, 11, 13, 15])
		
		bst.insert(12)
		assert(bst.order() == [-1, 2, 7, 9, 11, 12, 13, 15])
		
		bst.insert(21)
		assert(bst.order() == [-1, 2, 7, 9, 11, 12, 13, 15, 21])
		
		print("Done, test insertion OK!")

		
if __name__ == '__main__':
	test = BSTTest()
	#test.runTestInsert()
	#test.runTestSearch()
	#test.runTestMinimum()
	#test.runTestMaximum()
	#test.runTestSucessor()
	#test.runTestHeight()
	#test.runTestRemove()
	#test.runTestOrder()
	#test.runTestPreOrder()
	test.runTestPostOrder()
